using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace minega
{
    class NeighbourSolver
    {
        private UInt32 _width;
        private UInt32 _height;
        private Mines _mines;
        private CellStates _states;

        /// <summary>
        /// Stores which cells to process. 0 = don't process, 1 = do process, 2 = has been processed.
        /// Stores 4 cells per byte
        /// </summary>
        private byte[] _raw;
        private List<CellPos> _cache;
        private int _maxCache = 100000;

        public bool this[UInt32 x, UInt32 y]
        {
            get
            {
                UInt32 idx = x + y * _width;
                UInt32 rawIdx = idx / 8;
                byte rawInPos = (byte)(idx % 8);
                byte rawBits = (byte)(1 << rawInPos);

                return ((_raw[rawIdx] & rawBits) >> rawInPos) != 0;
            }
            set
            {
                UInt32 idx = x + y * _width;
                UInt32 rawIdx = idx / 8;
                byte rawInPos = (byte)(idx % 8);
                byte rawBits = (byte)(1 << rawInPos);
                byte val = (byte)(value ? 1 : 0);
                _raw[rawIdx] = (byte)(_raw[rawIdx] & ~rawBits | val << rawInPos);

                if (value)
                {
                    if (_cache.Count < _maxCache)
                        _cache.Add(new CellPos(x, y));
                }
            }
        }

        public NeighbourSolver(Mines mines, CellStates states)
        {
            _width = Convert.ToUInt32(mines.Width);
            _height = Convert.ToUInt32(mines.Height);
            _mines = mines;
            _states = states;

            _raw = new byte[(_width * _height + 7) / 8];
            _cache = new List<CellPos>(_maxCache);
        }

        public void Solve(uint x, uint y)
        {
            UInt32 c = 1;
            this[x, y] = true;
            while (c > 0)
            {
                CellPos pos = this.Pop();
                if (pos == null)
                    throw new Exception("That was strange...");
                this[pos.X, pos.Y] = false;
                c--;
                for (byte b = Neighbour.UL; b <= Neighbour.DR; b++)
                {
                    CellPos nPos = NeighbourPos.GetNeighbour2(b, pos.X, pos.Y, this._width, this._height);
                    if (nPos == null)
                        continue;

                    int iPosX = Convert.ToInt32(nPos.X);
                    int iPosY = Convert.ToInt32(nPos.Y);

                    if (_states[iPosX, iPosY] == CellStateFlags.Normal)
                    {
                        _states[iPosX, iPosY] = _mines.NeightbouringMines(iPosX, iPosY);
                        if (_states[iPosX, iPosY] == CellStateFlags.Open0)
                        {
                            this[nPos.X, nPos.Y] = true;
                            c++;
                        }
                    }
                }
            }
        }

        private CellPos Pop()
        {
            if (_cache.Count == 0)
            {
                for (UInt32 rawIdx = 0; rawIdx < _raw.Length; rawIdx++)
                {
                    if (_raw[rawIdx] != 0)
                    {
                        for (byte bit = 0; bit < 8; bit++)
                        {
                            if ((_raw[rawIdx] & (1 << bit)) != 0)
                            {
                                UInt32 idx = rawIdx * 8 + bit;
                                UInt32 y = idx / _width;
                                UInt32 x = idx % _width;

                                _cache.Add(new CellPos(x, y));
                                if (_cache.Count == _maxCache)
                                    break;
                            }
                        }
                    }
                    if (_cache.Count == _maxCache)
                        break;
                }
            }

            CellPos pos = _cache[0];
            _cache.RemoveAt(0);
            return pos;
        }
    }
}
